import java.util.*;

public class RandomizedSet {
    // 存储元素的值
    List<Integer> nums;
    // 记录每个元素对应在 nums 中的索引
    Map<Integer, Integer> valToIndex;
    /*这个哈希表在这里有什么用呢？
    * 为了能快速找到要删除的元素的索引下标*/

    public RandomizedSet() {
        nums = new ArrayList<>();
        valToIndex = new HashMap<>();
    }

    public boolean insert(int val) {
        // 若 val 已存在，不用再插入
        if (valToIndex.containsKey(val)) {
            return false;
        }
        // 若 val 不存在，插入到 nums 尾部，
        // 并记录 val 对应的索引值
        valToIndex.put(val, nums.size());
        nums.add(val);
        return true;
    }
    /*对于删除方法来说，哈希表和数组是各改各的（假设val的下标是2，nums.size()-1是5）
    * 数组是将5下标的元素和2下标的元素交换，使得val到数组末尾，方便删除。
    * 哈希表是将末尾元素对应的key值改为2，然后删除val
    * ——————————为什么哈希表也要修改下标？————————————
    * 当完成一次删除操作后，nums中的原末尾元素在2下标。所以哈希表中nums[2]对应的key
    * 也应该是2.以便于下次删除
    * */
    public boolean remove(int val) {
        // 若 val 不存在，不用再删除
        if (!valToIndex.containsKey(val)) {
            return false;
        }
        // 先拿到 val 的索引
        int index = valToIndex.get(val);
        // 将最后一个元素对应的索引修改为 index
        /*这里将最后一个元素的索引修改为index的方法是直接插入一个元素将其覆盖
        * 这样就将最后一个元素的索引改为index了*/
        valToIndex.put(nums.get(nums.size() - 1), index);
        // 交换 val 和最后一个元素
        Collections.swap(nums, index, nums.size() - 1);
        // 在数组中删除元素 val
        nums.remove(nums.size() - 1);
        // 删除元素 val 对应的索引
        valToIndex.remove(val);
        return true;
    }
    //Math.random() 函数返回的是一个0到1之间的随机浮点数。为了获取一个范围内的随机整数，您需要将其乘以范围的大小并进行类型转换。

    public int getRandom() {
        // 随机获取 nums 中的一个元素
        return nums.get((int) (Math.random() * nums.size()));
    }
}
